Field of the Invention
Embodiments of the present invention generally relate to acceleration of decision tree execution.
Description of the Related Art
Decision trees are typically traversed (executed) in a serial fashion. For each query, a decision tree is traversed by starting from the root node, evaluating the decision function on the query, and then moving on to the appropriate sub-tree. This is repeated until a leaf node is reached, which encodes the decision/classification result for the particular query.
Decision trees implemented thusly are well suited for scalar architectures that excel on conditional branching, such as the general purpose x86 and ARM microprocessors. However, decision trees are now commonly used to analyze data on parallel processors such as data and instruction parallel digital signal processors (DSPs), graphics processing units (GPUs), and vector processing engines. Accordingly, improving execution efficiency of decision trees on such processors is desirable.